package com.da.javatest.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenlida
 * @date 2019/2/26 20:12
 * @description
 */
public class Code390 {
    public static void main(String[] args) {
        System.out.println(new Code390().lastRemaining(100000000));
    }

    //public int lastRemaining(int n) {
    //    if (n < 2) {
    //        return n;
    //    }
    //    List<Integer> l = new ArrayList<>();
    //    for (int i = 2; i <= n; i += 2) {
    //        l.add(i);
    //    }
    //    return getOnly(l, l.size(), true);
    //}
    //
    //private int getOnly(List<Integer> l, int length, boolean flag) {
    //    int index = 0, i = 1;
    //    if (flag && length % 2 == 0) {
    //        i = 0;
    //    }
    //    for (; i < length; i += 2) {
    //        l.set(index++, l.get(i));
    //    }
    //    if (length == 1) {
    //        return l.get(0);
    //    }
    //    return getOnly(l, length / 2, !flag);
    //}
    public int f(int n) {
        return n == 1 ? 1 : 2 * b(n / 2);
    }

    public int b(int n) {
        if (n == 1) {
            return 1;
        }
        if (n % 2 == 0) {
            return f(n / 2) * 2 - 1;
        } else {
            return 2 * f(n / 2);
        }
    }

    public int lastRemaining(int n) {
        return f(n);
    }
}
